package com.leetcode.linkedList;

import com.leetcode.basic.ListNode;

import java.util.Random;

/**
 * @author Dennis Li
 * @date 2020/10/15 17:08
 */
public class RandomNode_382 {

    static class Solution {

        private ListNode head;
        private Random random;

        public Solution(ListNode head) {
            random = new Random();
            this.head = head;
        }

        public int getRandom() {
            ListNode cur = head;
            int i = 0, res = 0;
            while (cur != null) {
                // random取小于1的概率，即等于0，那么它的概率就等于 1 / n -- 数学推导证明
                if (random.nextInt(++i) < 1) {
                    res = cur.val;
                    // 不用break
//                    break;
                }
                cur = cur.next;
            }
            return res;
        }

    }

}
